<html>
<head><meta charset="utf-8"><title>Sort two Vec without allocating memory · general · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/index.html">general</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html">Sort two Vec without allocating memory</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="245437017"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245437017" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> hannahE2 <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245437017">(Jul 09 2021 at 12:38)</a>:</h4>
<p>I've started implementing iterators from lists, small vectors, etc. to learn how Iterator and their impls work. There is one thing I don't know how to do. In C++, I can just:</p>
<div class="codehilite" data-code-language="C++"><pre><span></span><code><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">char</span><span class="o">&gt;</span> <span class="n">v0</span><span class="p">{</span><span class="sc">'a'</span><span class="p">,</span><span class="sc">'b'</span><span class="p">,</span><span class="sc">'c'</span><span class="p">};</span>
<span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">v1</span><span class="p">{</span><span class="mi">2</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span><span class="mi">3</span><span class="p">};</span>
<span class="n">sort</span><span class="p">(</span><span class="n">zip</span><span class="p">(</span><span class="n">v0</span><span class="p">,</span> <span class="n">v1</span><span class="p">),</span> <span class="p">[](</span><span class="k">auto</span><span class="o">&amp;&amp;</span> <span class="n">p</span><span class="p">,</span> <span class="k">auto</span><span class="o">&amp;&amp;</span> <span class="n">q</span><span class="p">)</span> <span class="p">{</span> <span class="k">return</span> <span class="n">p</span><span class="p">.</span><span class="n">second</span><span class="p">()</span> <span class="o">&lt;</span> <span class="n">q</span><span class="p">.</span><span class="n">second</span><span class="p">();</span> <span class="p">});</span>
<span class="c1">// v0 = ['b', 'a', 'c']</span>
<span class="c1">// v1 = [1, 2, 3]</span>
</code></pre></div>
<p>and both vectors get sorted together, without allocating any extra memory, unnecessary memory transfers, etc. </p>
<p>How can I do this in Rust?</p>
<p>I don't seem to find a way to do this that doesn't require extra storage. I could allocate a third vector for storing a permutation, and then compute it, and then apply it twice, but that seems unnecessary. I could also allocate a vector of tuples, sort that, and then re-distribute the elements. </p>
<p>But how do I do this without using O(N) extra space ?</p>



<a name="245437878"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245437878" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245437878">(Jul 09 2021 at 12:47)</a>:</h4>
<p>zip isn't part of the c++ standard library, is it?</p>



<a name="245438002"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245438002" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Connor Horman <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245438002">(Jul 09 2021 at 12:48)</a>:</h4>
<p><span class="user-mention silent" data-user-id="330154">The 8472</span> <a href="#narrow/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory/near/245437878">said</a>:</p>
<blockquote>
<p>zip isn't part of the c++ standard library, is it?</p>
</blockquote>
<p>I'm pretty sure it was added with the rest of ranges</p>



<a name="245438159"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245438159" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245438159">(Jul 09 2021 at 12:49)</a>:</h4>
<p>I think it ended up postponed for C++23?</p>



<a name="245438447"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245438447" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245438447">(Jul 09 2021 at 12:52)</a>:</h4>
<p>I checked cppreference and didn't see it there, that's why I'm asking.</p>
<p>Anyway, the sort implementations in the rust standard library only operate on a single slice at a time. And rust iterators are single-pass (unless you clone them before use) so that wouldn't work great for sorting.</p>
<p>If that kind of external sorting exists it's probably in some library.</p>



<a name="245441684"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245441684" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> hannahE2 <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245441684">(Jul 09 2021 at 13:17)</a>:</h4>
<p><span class="user-mention silent" data-user-id="330154">The 8472</span> <a href="#narrow/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory/near/245437878">said</a>:</p>
<blockquote>
<p>zip isn't part of the c++ standard library, is it?</p>
</blockquote>
<p>Its available in range-v3 at least, I'm not really sure what's in C++17,20,23..</p>



<a name="245453037"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245453037" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Daniel Henry-Mantilla <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245453037">(Jul 09 2021 at 14:50)</a>:</h4>
<p>The basic thing to say is that C++ iterators are more like cursors / special slice ops than Rust iterators, which are a general-purpose state machine. I believe that <code>sort</code> implementation is taking advantage of arbitrary indexing, which is something not part of <code>Iterator</code>'s API.</p>



<a name="245497124"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245497124" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245497124">(Jul 09 2021 at 21:00)</a>:</h4>
<p><a href="https://stackoverflow.com/q/32564455/155423">How can I co-sort two Vecs based on the values in one of the Vecs?</a></p>



<a name="245536388"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245536388" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Laurențiu <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245536388">(Jul 10 2021 at 07:50)</a>:</h4>
<p>That still allocates, doesn't it?</p>



<a name="245676823"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245676823" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245676823">(Jul 12 2021 at 12:07)</a>:</h4>
<p>Ah, I missed that original caveat.</p>



<a name="245677394"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245677394" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245677394">(Jul 12 2021 at 12:13)</a>:</h4>
<p><span class="user-mention silent" data-user-id="232018">Daniel Henry-Mantilla</span> <a href="#narrow/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory/near/245453037">said</a>:</p>
<blockquote>
<p>I believe that <code>sort</code> implementation is taking advantage of arbitrary indexing, which is something not part of <code>Iterator</code>'s API.</p>
</blockquote>
<p>You could probably cobble together a quicksort  with <code>where I: DoubleEndedIterator + ExactSizeIterator + Clone, &lt;I as Iterator&gt;::Item = &amp;mut T</code> and <code>advance_by</code> once that's stable. For each recursion level you clone to get two copies and then advance them so you have two halves on which you can perform the next recursion level.<br>
It could work fine for <code>slice::IterMut</code> iterators. But if you pass a <code>vec::IntoIter&lt;Item=&amp;mut T&gt;</code> into it you'd end up with terrible terrible overhead due to the cloning.</p>



<a name="245678339"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245678339" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245678339">(Jul 12 2021 at 12:23)</a>:</h4>
<p>A pity we don't implement <code>Copy</code> on by-ref iterators to distinguish them from the more expensive owning ones.</p>



<a name="245678516"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245678516" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245678516">(Jul 12 2021 at 12:24)</a>:</h4>
<p>Wait... can you even Clone &amp;mut iterators? No would have to be a split method on them :/</p>



<a name="245678757"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245678757" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jake Goulding <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245678757">(Jul 12 2021 at 12:27)</a>:</h4>
<p>Copying iterators has empirically led to all sorts of problems.</p>



<a name="245680144"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122651-general/topic/Sort%20two%20Vec%20without%20allocating%20memory/near/245680144" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> The 8472 <a href="https://rust-lang.github.io/zulip_archive/stream/122651-general/topic/Sort.20two.20Vec.20without.20allocating.20memory.html#245680144">(Jul 12 2021 at 12:42)</a>:</h4>
<p>Yeah, I realized that this wouldn't help here anyway.</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>